跳到主要内容

JZ42 和为S的两个数字

https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b

第一次解：

import java.util.*;

public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
         if (array.length < 2) return new ArrayList<>();
        ArrayList<int[]> result = new ArrayList<>();

        int left = 0;
        int right = 1;
        int len = array.length;

        while(right < len) {
            int cur = array[left] + array[right];

            if (cur == sum) {
                result.add(new int[]{array[left], array[right]});
                left++; // 必须逼着 right 动
            } else if (cur < sum) {
                right++;
            } else {
                left++;
                right = left + 1;
            }
        }

        if (result.size() < 1) return new ArrayList<>();

        int[] min = result.get(0);

        for (int[] arr : result) {
            min = arr[0] * arr[1] > min[0] * min[1] ? min : arr;
        }

        ArrayList<Integer> temp = new ArrayList<>();
        temp.add(min[0]);
        temp.add(min[1]);
        return temp;
    }
}

总结：时间复杂度过高：是 log(n2)log(n^2)

第二次答题：

主要是：论证题目的隐含条件，输出两个数的乘积最小的。这句话的理解？

其实就证明外层的乘积更小 a + b = s; (a - m ) + (b + m) = s 则： (a - m ) (b + m) = a b - (b - a) m - m m < ab； 可以证明 m 越大乘积越小，说明外层的乘积更小。

因此采用夹逼策略，直接就能取得乘积最小的两个数

import java.util.ArrayList;
public class Solution {

    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> result = new ArrayList<>();
        // 使用双指针的做法（和前面那道题差不多，但是采用左右夹逼法
        int high = array.length - 1;
        int low = 0;
        
        // 因为是按递增排序的，所以只需调整两个指针位置就行了
        while (high > low) {
            int tmp = array[low] + array[high];
            if (tmp == sum) {
                result.add(array[low]);
                result.add(array[high]);
                break;
            } 
            //大于sum，说明太大了，high 左移寻找更小的数
            else if (tmp > sum) {
                high--;
            }
            //如果和小于sum，说明太小了，low 右移寻找更大的数
            else {
                low++;
            }
        }
        
        return result;
    }
}

时间复杂度变成了 log(n)log(n)